package 二分法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @PackageName: 二分法
 * @ClassName: LeetCode74
 * @Author: chen jinxu
 * @Date: 2022/2/27 22:50
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 * 每行中的整数从左到右按升序排列。
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
 * 输出：true
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
 * 输出：false
 *
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 100
 * -10^4 <= matrix[i][j], target <= 10^4
 */
public class LeetCode74 {
    public static void main(String[] args) {
        int[][] matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        int target = 11;
        boolean result = searchMatrix(matrix, target);
        System.out.println(result);
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        // 二维数组转一维数组
        int row = matrix.length;
        int col = matrix[0].length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                list.add(matrix[i][j]);
            }
        }
        int[] ints = list.stream().mapToInt(i -> i).toArray();
        int i = Arrays.binarySearch(ints, target);
        return i >= 0;
    }

}
